package com.wfm.leetcode.editor.cn;

/**
 * [3,4,-1,1]
 * 首先得把负数变成不需要处理的数字，赋值n+1，因为第20行说了if (num <= n)才处理
 * [3,4,5,1]
 * 每个位置的数字代表2个含义，负数代表下标数字出现过
 * 遍历到abs(3)，把index=2的数字变成负的  【3，4，-5，1】
 * 遍历到abs(4) 把index=3的数字变成负的    [3，4，-5，-1]
 * 遍历到abs(-5) 把index=4的变成负的，超过不需要操作
 * 遍历到abs(-1) 把index=0的变成负的 [-3，4，-5，-1]
 *
 * 再次遍历，发现只有第二个数字是正的，说明index+1的数字没出现
 */
public class PFour1缺失的第一个正数{
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        // 把负数变成不需要处理的正数
        for (int i = 0; i < n; ++i) {
            if (nums[i] <= 0) {
                nums[i] = n + 1;
            }
        }
        // 把出现的数字，对应的下标-1 的地方变成负的
        for (int i = 0; i < n; ++i) {
            int num = Math.abs(nums[i]);
            if (num <= n) {
                nums[num - 1] = -Math.abs(nums[num - 1]);
            }
        }
        // 找到正数，下标＋1就是答案
        for (int i = 0; i < n; ++i) {
            if (nums[i] > 0) {
                return i + 1;
            }
        }
        // [1,2,3,4] n=4，缺失5
        return n + 1;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) { 
        Solution solution = new PFour1缺失的第一个正数().new Solution();
    }
}